/**
 * @file   Graph.h
 * @author WinterMelonCDY <wintermeloncdy@wintermeloncdy-VirtualBox>
 * @date   Tue Dec 28 22:58:14 2021
 * 
 * @brief  
 * 
 * 
 */

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>

using namespace std;

template <typename T>
class Graph
{
private:
    int n;
    int m;
    T maximum = 0;
    vector<int> first;
    vector<int> next;
    vector<int> u;
    vector<int> v;
    vector<T> weight;

    bool is_adj(int i, int j) const
    {
        for (int k = 0; k < m; k++)
        {
            if ((u[k] == i && v[k] == j) || (u[k] == j && v[k] == i))
                return true;
        }
        return false;
    }

    const T &w(int i, int j) const
    {
        for (int k = 0; k < m; k++)
        {
            if ((u[k] == i && v[k] == j) || (u[k] == j && v[k] == i))
                return weight[k];
        }
        return maximum;
    }

    int deletemin(const vector<T> &dist, list<int> &heap)
    {
        list<int>::iterator tmp = heap.begin();
        int minimum = *heap.begin();
        for (list<int>::iterator it = heap.begin(); it != heap.end(); it++)
        {
            if (dist[*it - 1] < dist[minimum - 1])
            {
                minimum = *it;
                tmp = it;
            }
        }

        heap.erase(tmp);
        return minimum;
    }

public:
    Graph(int n1, int m1, int u1[], int v1[], T weight1[])
    {

        n = n1;
        m = m1;
        weight.resize(m);
        u.resize(m);
        v.resize(m);
        first.resize(n + 1);
        next.resize(m);
        for (int i = 0; i < m; i++)
        {
            next[i] = -1;
        }
        for (int i = 0; i < n; i++)
        {
            first[i] = -1;
        }
        for (int i = 0; i < m; i++)
        {
            u[i] = u1[i];
            v[i] = v1[i];
            next[i] = first[u[i]];
            first[u[i]] = i;
            weight[i] = weight1[i];
            maximum += weight[i];
        }
    }
    ~Graph(){};

    void print()
    {
        cout << m << "  " << n << endl;
        for (int i = 0; i < m; i++)
            cout << u[i] << " " << v[i] << " " << weight[i] << endl;
    }

    void Dijkstra(int id)
    {

        if (id < 1 || id > n)
            return;

        vector<T> dist(n, maximum);
        list<int> heap;
        for (int i = 0; i < n; i++)
        {
            heap.push_back(i + 1);
        }
        dist[id - 1] = 0;

        while (!heap.empty())
        {
            int key1 = deletemin(dist, heap);
            for (list<int>::iterator i = heap.begin(); i != heap.end(); i++)
            {
                int key2 = *i;
                if (is_adj(key1, key2))
                {
                    T tmp = dist[key1 - 1] + w(key1, key2);
                    if (dist[key2 - 1] > tmp)
                        dist[key2 - 1] = tmp;
                }
                else
                {
                }
            }
        }

        for (int i = 0; i < n; i++)
            cout << dist[i] << " ";
    }
};
